package unclassified.medium;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class IntegerReplacement_397 {

    public int integerReplacement(int n) {
        if (n == 1)
            return 0;
        Map<Long, Integer> map = new HashMap<>();
        Deque<Long> queue = new LinkedList<>();
        queue.offer((long) n);
        map.put((long) n, 0);
        while (!queue.isEmpty()) {
            Long poll = queue.poll();
            Integer step  = map.get(poll);
            long[] li = poll % 2 == 0 ? new long[] {poll / 2} : new long[] {poll - 1, poll + 1};
            for (long l : li) {
                if (l == 1)
                    return step  + 1;
                if (!map.containsKey(l)) {
                    queue.offer(l);
                    map.put(l, step  + 1);
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        IntegerReplacement_397 ing = new IntegerReplacement_397();
        System.out.println(ing.integerReplacement(4));
    }
}
